package algorithm;

/**
 * 字符串匹配算法  KMP
 *
 * @author miweidong
 * @date 2022-03-21 9:21
 */
public class KMP {

    public static void main(String[] args) {
        String original = "aaaaabababbbbaa";
        String target = "ababab";

        int force = bruteForce(original, target);
        System.out.println(force);

        int kmp = kmp(original, target);
        System.out.println(kmp);
    }

    /**
     * 字符串匹配暴力破解法
     *
     * @param original 原字符串
     * @param target   目标子串
     * @return 未匹配到返回-1  匹配成功，返回索引位置
     */
    public static int bruteForce(String original, String target) {
        int index = -1;
        for (int i = 0; i < original.length() - target.length() + 1; i++) {
            boolean flag = true;
            int m = i;
            for (int j = 0; j < target.length(); j++) {
                if (target.charAt(j) != original.charAt(m)) {
                    flag = false;
                    break;
                }
                m++;
            }
            if (flag) {
                index = i;
                break;
            }
        }
        return index;
    }


    /**
     * kmp串匹配优化
     *
     * @param original 原字符串
     * @param target   目标子串
     * @return 未匹配到返回-1  匹配成功，返回索引位置
     */
    public static int kmp(String original, String target) {
        int[] next = getNext(target);
        int i = 0, j = 0;
        while (i < original.length() && j < target.length()) {
            if (j == -1 || original.charAt(i) == target.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= target.length()) {
            return i - target.length();
        }
        return -1;
    }


    /**
     * 模式串（子串）的next数组求解
     *
     * @param pattern 模式串
     * @return 模式串next数组
     */
    public static int[] getNext(String pattern) {
        int[] arr = new int[pattern.length() + 1];
        int j = 0, k = -1;
        arr[0] = -1;
        while (j < pattern.length() - 1) {
            if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                j++;
                k++;
                arr[j] = k;
            } else {
                k = arr[k];
            }
        }
        return arr;
    }


}
